package com.flx.ark.algo;


import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

/**
 * @Author Fenglixiong
 * @Create 2022/6/30 15:54
 * @Description
 **/
public class FindMaxValue {

    /**
     * 算法思路：先将100w数据分成10份，每一份找到10个最大值，最后是100个数据，再选出其中最大的10个即可。
     * 对每一份10w数据使用小根堆找到最大的10个数字，先构建10个数字的小根堆，然后遍历剩下的数据，比跟节点大的进入小根堆继续调整
     * @param args
     */
    public static void main(String[] args) throws ExecutionException, InterruptedException {

        ExecutorService executorService = Executors.newFixedThreadPool(10);

        List<Integer> dataList = new ArrayList<>();
        //填充数据
        for(int i=0;i<1000000; i++){
            dataList.add(i+1);
        }

        //线程结果列表
        List<Future<List<Integer>>> resultFuture = new ArrayList<>();
        for(int i=0;i<9;i++){
            List<Integer> subList = dataList.subList(i*100000,(i+1)*100000);
            resultFuture.add(executorService.submit(new MyTask(subList)));
        }

        //最终100个数字
        List<Integer> resultList = new ArrayList<>();
        //获取结果列表
        for (int i = 0; i < resultFuture.size(); i++) {
            resultList.addAll(resultFuture.get(i).get());
        }

        //在最终的100个数字中获取最大10个数据
        List<Integer> result = findMax10(resultList);
        System.out.println(result);

        //关闭线程池
        executorService.shutdown();

    }

    //任务线程
    static class MyTask implements Callable<List<Integer>> {

        private List<Integer> taskList;

        public MyTask(List<Integer> taskList) {
            this.taskList = taskList;
        }

        @Override
        public List<Integer> call() throws Exception {
            //针对每个线程需要处理的10w数据进行处理
            return findMax10(taskList);
        }
    }

    //获取数据中最大的10个数字
    public static List<Integer> findMax10(List<Integer> taskList){

        if (taskList == null || taskList.size() < 10) {
            return taskList;
        }
        //构建长度为10的大顶堆
        int[] res = new int[10];
        for (int i = 0; i < 10; i++) {
            res[i] = taskList.get(i);
        }

        //遍历读取每一个数值
        for (int j = 10; j < taskList.size(); j++) {
            if (taskList.get(j) >= res[0]) continue;//大于顶元素(最大值)
            res[0] = taskList.get(j);
            adjustHeapForMaxTop(res, 0, res.length);
        }

        List<Integer> resultList = new ArrayList<>();
        for (int i=0;i<res.length;i++){
            resultList.add(res[i]);
        }

        return resultList;
    }

    //调整大跟堆
    public static void adjustHeapForMaxTop(int[] arr, int root, int len) {
        int index = root * 2 + 1;
        if (index >= len) return;
        int rootVal = arr[root];
        while (index < len) {
            if (index + 1 < len && arr[index + 1] > arr[index]) index++;
            if (rootVal >= arr[index]) break;
            arr[root] = arr[index];
            root = index;
            index = index * 2 + 1;
        }
        arr[root] = rootVal;
    }



}
